package com.ma.tree;

import javax.xml.stream.events.StartDocument;
import java.util.LinkedList;
import java.util.Queue;

public class Serialize {


    /**
     * 用先序遍历方式
     * 将二叉树序列化为队列
     * @param head
     * @return
     */
    public static Queue<String> preSerialize(Node head){
        Queue<String> ans=new LinkedList<>();
        pres(head,ans);
        return ans;
    }

    public static void pres(Node head, Queue<String> ans){
        if(head==null){
            ans.add(null);
        }else {
            ans.add(String.valueOf(head.value));
            pres(head.left,ans);
            pres(head.right,ans);
        }
    }

    /**
     * 先序遍历方式
     * 反序列化队列创建二叉树
     * @param ans
     * @return
     */
    public static Node buildByPreQueue(Queue<String> ans){
        if(ans==null||ans.size()==0){
            return null;
        }
        return preb(ans);
    }

    private static Node preb(Queue<String> ans) {
        String value=ans.poll();
        if(value==null){
            return null;
        }
        Node head=new Node(Integer.parseInt(value));
        head.left=preb(ans);
        head.right=preb(ans);
        return head;
    }


    /**
     * 用按层遍历的方式
     * 将二叉树序列化为队列
     * @param head
     * @return
     */
    public static Queue<String> levelSerialize(Node head){
        Queue<String> ans=new LinkedList<>();
        if(head==null){
            ans.add(null);
        }else {
            ans.add(String.valueOf(head.value));
            Queue<Node> queue=new LinkedList<>();
            queue.add(head);
            while (!queue.isEmpty()){
                head=queue.poll();
                if(head.left!=null){
                    ans.add(String.valueOf(head.left.value));
                    queue.add(head.left);
                }else {
                    ans.add(null);
                }
                if(head.right!=null){
                    ans.add(String.valueOf(head.right.value));
                    queue.add(head.right);
                }else {
                    ans.add(null);
                }
            }
        }
        return ans;
    }


    /**
     * 按层遍历方式
     * 反序列化队列创建二叉树
     * @param ans
     * @return
     */
    public static Node buildByLevelQueue(Queue<String> ans){
       if(ans==null||ans.size()==0){
           return null;
       }
       Node head=generateNode(ans.poll());



       Queue<Node> queue=new LinkedList<Node>();
       if(head!=null){
           queue.add(head);
       }
       Node node=null;
       while (!queue.isEmpty()){
           node =queue.poll();
           node.left=generateNode(ans.poll());
           node.right=generateNode(ans.poll());
           if(node.left!=null){
               queue.add(null);
           }
           if(node.right!=null){
               queue.add(null);
           }
       }
       return head;
    }

    public static Node generateNode(String val){
        if(val==null){
            return null;
        }
        return new Node(Integer.parseInt(val));

    }

}
